|
BlooP and FlooP are simple programming languages designed by Douglas Hofstadter to illustrate a point in his book ''Gödel, Escher, Bach''.〔Douglas Hofstadter (1979), ''Gödel, Escher, Bach'', Basic Books, Chapter XIII.〕 BlooP is a non-Turing-complete programming language whose main control flow structure is a bounded loop (i.e. recursion is not permitted). All programs in the language must terminate, and this language can only express primitive recursive functions.〔(Stanford Encyclopedia of Philosophy: Computability and Complexity )〕 FlooP is identical to BlooP except that it supports unbounded loops; it is a Turing-complete language and can express all computable functions. For example, it can express the Ackermann function, which (not being primitive recursive) cannot be written in BlooP. Borrowing from standard terminology in mathematical logic,〔Hofstadter (1979), p. 424.〕〔Thomas Forster (2003), ''(Logic, Induction and Sets )'', Cambridge University Press, p. 130.〕 Hofstadter calls FlooP's unbounded loops MU-loops. Like all Turing-complete programming languages, FlooP suffers from the halting problem: programs might not terminate, and it is not possible, in general, to decide which programs do. BlooP and FlooP can be regarded as models of computation, and have sometimes been used in teaching computability.〔David Mix Barrington (2004), CMPSCI 601: Theory of Computation, University of Massachusetts Amherst, (Lecture 27 ).〕 ==BlooP examples== The only variables are output (the return value of the procedure) and cell(''i'') (an unbounded sequence of natural-number variables, indexed by constants, as in the Unlimited Register Machine〔Hofstadter refers to these cells as a set of "auxiliary variables."〕). The only operators are ⇐ (assignment), + (addition), × (multiplication), < (less-than), > (greater-than) and = (equals).Each program uses only a finite number of cells, but the numbers in the cells can be arbitrarily large. Data structures such as lists or stacks can be handled by interpreting the number in a cell in specific ways, that is, by Gödel numbering the possible structures. Control flow constructs include bounded loops, conditional statements, ABORT jumps out of loops, and QUIT jumps out of blocks. BlooP does not permit recursion, unrestricted jumps, or anything else that would have the same effect as the unbounded loops of FlooP. Named procedures can be defined, but these can call only previously defined procedures.〔Hofstadter (1979), p. 413.〕抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「BlooP and FlooP」の詳細全文を読む スポンサード リンク
|